package com.shm.leetcode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 剑指 Offer 61. 扑克牌中的顺子
 * 从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: [1,2,3,4,5]
 * 输出: True
 *  
 *
 * 示例 2:
 *
 * 输入: [0,0,1,2,5]
 * 输出: True
 *  
 *
 * 限制：
 *
 * 数组长度为 5 
 *
 * 数组的数取值为 [0, 13] .
 *
 * 作者：Krahets
 * 链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/57mpoj/
 * @author SHM
 */
public class IsStraight {
    /**
     * 解题思路：
     * 根据题意，此 55 张牌是顺子的 充分条件 如下：
     *
     * 除大小王外，所有牌 无重复 ；
     * 设此 55 张牌中最大的牌为 maxmax ，最小的牌为 minmin （大小王除外），则需满足：
     * max - min < 5
     * max−min<5
     *
     * 因此可将问题转化为：此 55 张牌是否满足以上两个条件？
     *
     *
     *
     * 方法一： 集合 Set + 遍历
     * 遍历五张牌，遇到大小王（即 00 ）直接跳过。
     * 判别重复： 利用 Set 实现遍历判重， Set 的查找方法的时间复杂度为 O(1)O(1) ；
     * 获取最大 / 最小的牌： 借助辅助变量 mama 和 mimi ，遍历统计即可。
     * 复杂度分析：
     * 时间复杂度 O(1)O(1) ： 本题中给定牌数量 N \equiv 5N≡5 ；遍历数组使用 O(N) = O(5) = O(1)O(N)=O(5)=O(1) 时间。
     * 空间复杂度 O(1)O(1) ： 用于判重的辅助 Set 使用 O(N) = O(1)O(N)=O(1) 额外空间。
     *
     * 作者：Krahets
     * 链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/572x9r/
     * @param nums
     * @return
     */
    public boolean isStraight_1(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int max = 1,min =14;
        for (int i = 0; i < 5; i++) {
            if(nums[i]==0){
                continue;
            }
            if(nums[i]>max){
                max = nums[i];
            }
            if(nums[i]<min){
                min = nums[i];
            }
            //若有重复，提前返回 false
            if(set.contains(nums[i])){
                return false;
            }
            set.add(nums[i]);
        }
        return max-min<5;
    }

    /**
     * 方法二：排序 + 遍历
     * 先对数组执行排序。
     * 判别重复： 排序数组中的相同元素位置相邻，因此可通过遍历数组，判断 nums[i] = nums[i + 1]nums[i]=nums[i+1] 是否成立来判重。
     * 获取最大 / 最小的牌： 排序后，数组末位元素 nums[4]nums[4] 为最大牌；元素 nums[joker]nums[joker] 为最小牌，其中 jokerjoker 为大小王的数量。
     * 复杂度分析：
     * 时间复杂度 O(1)O(1) ： 本题中给定牌数量 N \equiv 5N≡5 ；数组排序使用 O(N \log N) = O(5 \log 5) = O(1)O(NlogN)=O(5log5)=O(1) 时间。
     * 空间复杂度 O(1)O(1) ： 变量 jokerjoker 使用 O(1)O(1) 大小的额外空间。
     *
     * 作者：Krahets
     * 链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/572x9r/
     * @param nums
     * @return
     */
    public boolean isStraight(int[] nums) {
        int j=0;
        Arrays.sort(nums);
        for(int i =0;i<nums.length-1;i++){
            if(nums[i]==0){
                j++;
            }else if(nums[i]==nums[i+1]){
//                若有重复，提前返回 false
                return false;
            }
        }
        return nums[4]-nums[j]<5;
    }
}
